package own.stu.jobgib.playown.alg.solution.preSum;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1. 前缀和
 * 数组：a[i] 长度n <br/>
 * idx       :  0    1   2   3   .... n - 1    n    <br/>
 * a[i]      :a[0] a[1] a[2] a[3]. ... a[n-1]       <br/>
 * preSum[i] : 0   p[1] p[2] p[3] .... p[n-1] p[n]  <br/>
 * p[i + 1] 表示前 i个 数组元素的和 a[0] ... a[i], 之所以以1为开头，是为了方便计算第一个元素的前缀和 p[1] - p[0] = a[0]
 * 计算区间的 i - j 的和，p[j + 1] - p[i], 此时只需要o(1)，如果遍历a[i]...a[j]的时间复杂度为o(n)
 * <p/>
 * <p>
 * 2. 前缀和异或 (异或：a^a=0, a^0=a)
 * ex:
 * 0~3的元素异或为  s1 = a[0]^a[1]^a[2]^a[3]
 * 0~7的元素异或为  s2 = a[0]^a[1]^a[2]^a[3]...a[6]^a[7]
 * <p>
 * s1^s2 = a[4]^a[5]^a[6]^a[7] 即为 4~7的异或（跟前缀和的性质类似）
 * <p/>
 * 3. 前缀和 与 mod 使用，可以求乘积或者整除问题
 */
public class PreSum {

    public static void main(String[] args) {
        PreSum p = new PreSum();
        /*System.out.println(p.subarraySum(new int[]{0, 0}, 0));
        System.out.println(p.subarraySum(new int[]{1}, 0));
        System.out.println(p.subarraySum(new int[]{1, 1, 1, 1, -1, 1, -1, 0, 1, -1}, 0));*/

        System.out.println(p.subarraysDivByK(new int[]{4, 5, 0, -2, -3, 1}, 5));
    }

    /**
     * 560. 和为 K 的子数组
     * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
     * <p>
     * 子数组是数组中元素的连续非空序列。
     * <p>
     * 示例 1：
     * 输入：nums = [1,1,1], k = 2
     * 输出：2
     * <p>
     * 示例 2：
     * 输入：nums = [1,2,3], k = 3
     * 输出：2
     */
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>(); // preSum : cnt
        // map.put(0, 1);
        int preSum = 0;
        // 举个例子 来模拟下
        for (int i : nums) {
            preSum += i;
            if (preSum == k) {
                ans += 1;
            }
            ans += map.getOrDefault(preSum - k, 0);
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return ans;
    }

    /**
     * 974. 和可被 K 整除的子数组
     * 给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。
     * 子数组 是数组的 连续 部分。
     * <p>
     * 示例 1：
     * 输入：nums = [4,5,0,-2,-3,1], k = 5
     * 输出：7
     * 解释：
     * 有 7 个子数组满足其元素之和可被 k = 5 整除：
     * [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
     */
    public int subarraysDivByK(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ans = 0, preSum = 0;
        // (a - b) % k == 0 ==> a % k - b % k == 0 == > a%k == b % k
        int[] map = new int[k]; // 存放mod的（余数）的个数
        //map[0] = 1;
        for (int i : nums) {
            preSum += i;
            int mod = (preSum % k + k) % k;// 负数的情况， -6 % 5 = -1，放入map会异常

            if (mod == 0) {
                ans += 1;
            }
            ans += map[mod];
            map[mod]++;
        }
        return ans;
    }

    /**
     * 1590. 使数组和能被 P 整除
     * 给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
     * 请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
     * 子数组 定义为原数组中连续的一组元素。
     * <p>
     * 示例 1：
     * 输入：nums = [3,1,4,2], p = 6
     * 输出：1
     * 解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。
     */
    public int minSubarray(int[] nums, int p) {
        if (nums == null || nums.length == 0 || p <= 0) {
            return 0;
        }

        long sum = 0;
        for (int i : nums) {
            sum += i;
        }
        if (sum < p) return -1;
        int x = (int) (sum % p); // 注意越界
        if (x == 0) return 0;

        int ans = nums.length;
        int preSum = 0;
        Map<Integer, Integer> map = new HashMap<>();// idx: mod; val_0: mod的最近的一个idx of nums
//        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            preSum = (preSum + num) % p;
            if (preSum == x) {
                ans = Math.min(ans, i + 1);
            }
            map.put(preSum, i);
            int mod = (preSum - x + p) % p;
            Integer idx = map.get(mod);
            if (idx != null) {
                ans = Math.min(ans, i - idx);
            }
        }

        return ans < nums.length ? ans : -1;
    }

    /**
     * 1371. 每个元音包含偶数次的最长子字符串
     * 给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
     * <p>
     * 示例 1：
     * 输入：s = "eleetminicoworoep"
     * 输出：13
     * 解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
     */
    public int findTheLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // 5个int数字表示 a~u的奇偶状态，一共32个状态
        // 根据题意：每个字符（a~u)都是偶数，又因为奇数-奇数 = 偶数，偶数-偶数=偶数
        // 因此可以考虑保持每个状态的最左的下标，下一次遇到同样的状态，就是奇偶都一样，那么这段距离中，a~u的个数都是偶数的。
        int[] states = new int[1 << 5];
        Arrays.fill(states, -1);
        states[0] = 0; // a ~ e 都是 偶数（0）
        int st = 0;
        int ans = 0;
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {

            char c = cs[i];
            if (c == 'a') {
                st ^= 1 << 0;
            } else if (c == 'e') {
                st ^= 1 << 1;
            } else if (c == 'i') {
                st ^= 1 << 2;
            } else if (c == 'o') {
                st ^= 1 << 3;
            } else if (c == 'u') {
                st ^= 1 << 4;
            }
            // 这里很巧妙，将非a~u的字符也纳入计算中
            if (states[st] != -1) {
                ans = Math.max(ans, i + 1 - states[st]);
            } else {
                states[st] = i + 1;
            }
        }
        return ans;
    }

    /**
     * 1542. 找出最长的超赞子字符串
     * 给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
     * <p>
     * 「超赞子字符串」需满足满足下述两个条件：
     * 该字符串是 s 的一个非空子字符串
     * 进行任意次数的字符交换后，该字符串可以变成一个回文字符串
     * <p>
     * 示例 1：
     * 输入：s = "3242415"
     * 输出：5
     * 解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"
     */
    public int longestAwesome(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int ans = 0;
        int[] states = new int[1 << 10];
        Arrays.fill(states, -1);
        char[] cs = s.toCharArray();
        int st = 0;// 空串 （0~9）都是偶数（都是0个)
        states[0] = 0;

        for (int i = 0; i < cs.length; i++) {
            int vc = cs[i] - '0';
            st ^= 1 << vc;
            int idx = states[st];
            // states[i] == states[j] 表示相同的状态出现过，那么区间（map[states[i]], map[states[j]]) 的所有数字都出现偶数个
            if (idx != -1) {
                ans = Math.max(i + 1 - idx, ans);
            } else {
                states[st] = i + 1;
            }
            // states[i] 与 states[j] 中间有一位不同的时候，表示那么区间（map[states[i]], map[states[j]]) 的数字中有一个数字是奇数的，其他都出现偶数个
            for (int j = 0; j < 10; j++) {
                int cur = st ^ (1 << j);
                idx = states[cur];
                if (idx != -1) {
                    ans = Math.max(i + 1 - idx, ans);
                }
            }
        }

        return ans == 0 ? 1 : ans;
    }
}
